package innersort;

/*
 * 快速排序
 * */
public class QuickSort2 extends BaseSort {
    public static void main(String[] args) {
        int[] array = {23, 45, 17, 11, 13, 89, 72, 26, 3, 17, 11, 13};
        sort(array, 0, array.length - 1);
    }

    private static int[] sort(int[] array, int left, int right) {
        int len = array.length,
                partitionIndex;

        if (left < right) {
            partitionIndex = partition(array, left, right);
            sort(array, left, partitionIndex - 1);
            sort(array, partitionIndex + 1, right);
        }
        return array;
    }

    private static int partition(int[] array, int left, int right) {     // 分区操作
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (array[i] < array[pivot]) {
                exchange(array, i, index);
                print(array, array[pivot], i, index);
                index++;
            } else {
                print(array, array[pivot], i, index);
            }
        }
        exchange(array, pivot, index - 1);
        print(array, array[pivot], pivot, index - 1);
        System.out.println("-----------------------------------------------------------------------------");
        return index - 1;
    }
}
